{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Constrained Subsequence Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #queue #array #dynamic-programming #sliding-window #monotonic-queue #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #队列 #数组 #动态规划 #滑动窗口 #单调队列 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: constrainedSubsetSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #带限制的子序列和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>&nbsp;和一个整数&nbsp;<code>k</code>&nbsp;，请你返回 <strong>非空</strong>&nbsp;子序列元素和的最大值，子序列需要满足：子序列中每两个 <strong>相邻</strong>&nbsp;的整数&nbsp;<code>nums[i]</code>&nbsp;和&nbsp;<code>nums[j]</code>&nbsp;，它们在原数组中的下标&nbsp;<code>i</code>&nbsp;和&nbsp;<code>j</code>&nbsp;满足&nbsp;<code>i &lt; j</code>&nbsp;且 <code>j - i &lt;= k</code> 。</p>\n",
    "\n",
    "<p>数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [10,2,-10,5,20], k = 2\n",
    "<strong>输出：</strong>37\n",
    "<strong>解释：</strong>子序列为 [10, 2, 5, 20] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [-1,-2,-3], k = 1\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>子序列必须是非空的，所以我们选择最大的数字。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [10,-2,-10,-5,20], k = 2\n",
    "<strong>输出：</strong>23\n",
    "<strong>解释：</strong>子序列为 [10, -2, -5, 20] 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 10^5</code></li>\n",
    "\t<li><code>-10^4&nbsp;&lt;= nums[i] &lt;= 10^4</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [constrained-subsequence-sum](https://leetcode.cn/problems/constrained-subsequence-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [constrained-subsequence-sum](https://leetcode.cn/problems/constrained-subsequence-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,2,-10,5,20]\\n2', '[-1,-2,-3]\\n1', '[10,-2,-10,-5,20]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        dp = [0] * len(nums)\n",
    "        dq = deque()\n",
    "        ans = -inf\n",
    "        for i in range(len(nums)):\n",
    "            while dq and dq[0] < i - k:\n",
    "                dq.popleft()\n",
    "            if dq:\n",
    "                dp[i] = nums[i] + dp[dq[0]]\n",
    "            else:\n",
    "                dp[i] = nums[i]\n",
    "            if dp[i] > 0:\n",
    "                while dq and dp[dq[-1]] <= dp[i]:\n",
    "                    dq.pop()\n",
    "                dq.append(i)\n",
    "           \n",
    "            ans = max(dp[i], ans)\n",
    "            \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        q = deque()\n",
    "        n = len(nums)\n",
    "        ans = max(nums)\n",
    "        for i in range(n):\n",
    "            while q and i - q[0][1] > k:\n",
    "                q.popleft()\n",
    "            \n",
    "            cur = max(nums[i], nums[i] + (q[0][0] if q else 0))\n",
    "            ans = max(ans, cur)\n",
    "            while q and cur >= q[-1][0]:\n",
    "                q.pop()\n",
    "            q.append((cur, i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        q = deque()\n",
    "        n = len(nums)\n",
    "        ans = nums[0]\n",
    "        for i in range(n):\n",
    "            while q and i - q[0][1] > k:\n",
    "                q.popleft()\n",
    "            \n",
    "            cur = nums[i] + (q[0][0] if q and q[0][0] > 0 else 0)\n",
    "            ans = max(ans, cur)\n",
    "            while q and cur >= q[-1][0]:\n",
    "                q.pop()\n",
    "            q.append((cur, i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        res = -inf\n",
    "\n",
    "        q = deque()\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            while q and q[0][0] + k < i:\n",
    "                q.popleft()\n",
    "            cur = x + max(0, (0 if not q else q[0][1]))\n",
    "            res = max(res, cur)\n",
    "            while q and q[-1][1] <= cur:\n",
    "                q.pop()\n",
    "            q.append((i, cur))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = -inf\n",
    "        stack = deque()\n",
    "        for i in range(n):\n",
    "            while stack and stack[0][0] < i-k:\n",
    "                stack.popleft()\n",
    "            cur = nums[i]\n",
    "            if stack and stack[0][1] > 0:\n",
    "                cur += stack[0][1]\n",
    "            if cur > ans:\n",
    "                ans =cur\n",
    "            while stack and stack[-1][1] <= cur:\n",
    "                stack.pop()\n",
    "            stack.append([i, cur])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "def I():\n",
    "    return input()\n",
    "\n",
    "def II():\n",
    "    return int(input())\n",
    " \n",
    "def MII():\n",
    "    return map(int, input().split())\n",
    " \n",
    "def LI():\n",
    "    return list(input().split())\n",
    " \n",
    "def LII():\n",
    "    return list(map(int, input().split()))\n",
    " \n",
    "def GMI():\n",
    "    return map(lambda x: int(x) - 1, input().split())\n",
    " \n",
    "def LGMI():\n",
    "    return list(map(lambda x: int(x) - 1, input().split()))\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        dq = Deque()\n",
    "        ans = -int(1e9)\n",
    "        for i,x in enumerate(nums):\n",
    "            while dq and dq[0][1] < i-k:\n",
    "                dq.popleft()\n",
    "            if dq:\n",
    "                x = max(x, dq[0][0] + x)\n",
    "            while dq and x >= dq[-1][0]:\n",
    "                dq.pop()\n",
    "            dq.append((x,i))\n",
    "            ans = max(ans, x)\n",
    "        return ans\n",
    "\n",
    "# end-------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        res = -inf\n",
    "\n",
    "        q = deque()\n",
    "        q.append((-1, 0))\n",
    "\n",
    "        for i, x in enumerate(nums):\n",
    "            while q and q[0][0] + k < i:\n",
    "                q.popleft()\n",
    "            cur = x + max(0, (0 if not q else q[0][1]))\n",
    "            res = max(res, cur)\n",
    "            while q and q[-1][1] <= cur:\n",
    "                q.pop()\n",
    "            q.append((i, cur))\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = max(nums)\n",
    "        if res <= 0:\n",
    "            return res\n",
    "        cur = 1\n",
    "        dq = deque([0])\n",
    "        while cur < n:\n",
    "            while len(dq) and dq[0]+k < cur:\n",
    "                dq.popleft()\n",
    "            nums[cur] = max(nums[dq[0]], 0) + nums[cur]\n",
    "            res = max(res, nums[cur])\n",
    "            while len(dq) and nums[dq[-1]] <= nums[cur]:\n",
    "                dq.pop()\n",
    "            dq.append(cur)\n",
    "            cur += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        q = deque()\n",
    "        res = -inf\n",
    "        for i, x in enumerate(nums):\n",
    "            while q and q[0][1] < i - k:\n",
    "                q.popleft()\n",
    "            if q:\n",
    "                x = max(x, q[0][0] + x)\n",
    "            while q and x >= q[-1][0]:\n",
    "                q.pop()\n",
    "            q.append((x, i))\n",
    "            res = max(res, x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        q = deque()\n",
    "        n = len(nums)\n",
    "        ans = max(nums)\n",
    "        for i in range(n):\n",
    "            while q and i - q[0][1] > k:\n",
    "                q.popleft()\n",
    "            \n",
    "            cur = nums[i] + (q[0][0] if q and q[0][0] > 0 else 0)\n",
    "            ans = max(ans, cur)\n",
    "            while q and cur >= q[-1][0]:\n",
    "                q.pop()\n",
    "            q.append((cur, i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = max(nums)\n",
    "        deq = deque()\n",
    "        for i, x in enumerate(nums):\n",
    "            if deq and i - k - 1 == deq[0][0]:\n",
    "                deq.popleft()\n",
    "            if deq:\n",
    "                ans = max(ans, deq[0][1] + x)\n",
    "            tmp = deq[0][1] + x if deq and deq[0][1] > 0 else x\n",
    "            while deq and deq[-1][1] <= tmp:\n",
    "                deq.pop()\n",
    "            deq.append((i, tmp))\n",
    "            # print(deq)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# dp[i] := maximum sum of constrained subsequence end at nums[i]\r\n",
    "# dp[0] = nums[0]\r\n",
    "# dp[i] = nums[i] + max(0, dp[j], i - k <= j < i)\r\n",
    "from collections import deque\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\r\n",
    "        res = -10001\r\n",
    "        dp: deque[tuple[int, int]] = deque()\r\n",
    "\r\n",
    "        for i, num in enumerate(nums):\r\n",
    "            while dp and dp[0][0] < i - k:\r\n",
    "                dp.popleft()\r\n",
    "            if dp: num += dp[0][1]\r\n",
    "\r\n",
    "            if num > 0:\r\n",
    "                while dp and dp[-1][-1] <= num:\r\n",
    "                    dp.pop()\r\n",
    "                dp.append((i, num))\r\n",
    "            \r\n",
    "            res = max(res, num)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        stack = [[nums[0], 0]]\n",
    "        ans = nums[0]\n",
    "        for i in range(1,n):\n",
    "            while stack and (stack[0][1] < i - k or stack[0][0] <= 0):\n",
    "                stack.pop(0)\n",
    "            if not stack:\n",
    "                if nums[i] > ans:\n",
    "                    ans = nums[i]\n",
    "                if nums[i] > 0:\n",
    "                    stack.append([nums[i], i])\n",
    "            else:\n",
    "                cur = stack[0][0] + nums[i]\n",
    "                if cur > ans:\n",
    "                    ans = cur\n",
    "                while stack and stack[-1][0] <= cur:\n",
    "                    stack.pop(-1)\n",
    "                if cur > 0:\n",
    "                    stack.append([cur, i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        ans=-99999999;pq=deque()\n",
    "        for i,j in enumerate(nums):\n",
    "            if(len(pq) and pq[0][0]>0):x=pq[0][0]+j\n",
    "            else:x=j\n",
    "            ans=max(ans,x)\n",
    "            while(len(pq) and pq[0][1]<=i-k):pq.popleft()\n",
    "            while(len(pq) and pq[-1][0]<=x):pq.pop()\n",
    "            pq.append((x,i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        stack = deque([[nums[0], 0]])\n",
    "        ans = nums[0]\n",
    "        for i in range(1, n):\n",
    "            while stack and stack[0][1] < i - k:\n",
    "                stack.popleft()\n",
    "            cur = max(stack[0][0] + nums[i], nums[i])\n",
    "            ans = ans if ans > cur else cur\n",
    "            while stack and stack[-1][0] <= cur:\n",
    "                stack.pop()\n",
    "            stack.append([cur, i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    ## 超时\n",
    "    def constrainedSubsetSum0(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i] = nums[i]\n",
    "            for j in range(i):\n",
    "                if i - j <= k:\n",
    "                    dp[i] = max(dp[i], dp[j] + nums[i])\n",
    "        # print(dp)\n",
    "        return max(dp)\n",
    "\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        ans = nums[0]\n",
    "        dp[0] = nums[0]\n",
    "\n",
    "        #单调队列\n",
    "        q = collections.deque([0])\n",
    "\n",
    "        for i in range(1,n):\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "\n",
    "            dp[i] = max(dp[q[0]],0) + nums[i]\n",
    "            ans = max(ans, dp[i])\n",
    "\n",
    "            while q and dp[i] >= dp[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        #第n个数字，最大值\n",
    "        answer = nums[0]\n",
    "        record = [nums[0]]\n",
    "        m, mi = nums[0], 0\n",
    "        s = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            res = nums[i]\n",
    "            if m > 0:\n",
    "                res += m\n",
    "            record.append(res)\n",
    "            if res >= m:\n",
    "                mi = len(record) - 1\n",
    "                m = res\n",
    "            answer = max(answer, res)\n",
    "            if len(record) - s > k:\n",
    "                s += 1\n",
    "                if mi < s:\n",
    "                    for j in range(s, len(record)):\n",
    "                        if mi < s or record[j] >= m:\n",
    "                            mi = j\n",
    "                            m = record[j]\n",
    "                    \n",
    "        #print(dp)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = [0] * 100010\n",
    "        hh, tt = 0, -1\n",
    "        f = [0] * n\n",
    "        ans = -inf\n",
    "        for i in range(n):\n",
    "            while hh <= tt and i - q[hh] > k:\n",
    "                hh += 1\n",
    "            f[i] = nums[i]\n",
    "            if hh <= tt:\n",
    "                f[i] = max(f[i], nums[i] + f[q[hh]])\n",
    "            while hh <= tt and f[i] >= f[q[tt]]:\n",
    "                tt -= 1\n",
    "            tt += 1\n",
    "            q[tt] = i\n",
    "            ans = max(ans, f[i])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = [0] * 100010\n",
    "        hh, tt = 0, -1\n",
    "        f = [-inf] * n\n",
    "        ans = -inf\n",
    "        for i in range(n):\n",
    "            while hh <= tt and i - q[hh] > k:\n",
    "                hh += 1\n",
    "            f[i] = nums[i]\n",
    "            if hh <= tt:\n",
    "                f[i] = max(f[i], nums[i] + f[q[hh]])\n",
    "            while hh <= tt and f[i] >= f[q[tt]]:\n",
    "                tt -= 1\n",
    "            tt += 1\n",
    "            q[tt] = i\n",
    "            ans = max(ans, f[i])\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [nums[i] for i in range(n)] \n",
    "        dq = collections.deque()\n",
    "        for i in range(n):\n",
    "            while dq and i - dq[0] > k:\n",
    "                dq.popleft()\n",
    "            if dq:\n",
    "                dp[i] = max(dp[i], dp[dq[0]] + nums[i])\n",
    "            while dq and dp[i] >= dp[dq[-1]]:\n",
    "                dq.pop()\n",
    "            dq.append(i)\n",
    "        return max(dp)\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = deque()\n",
    "        dp = [num for num in nums]\n",
    "        for i in range(n):\n",
    "            if q:\n",
    "                # 因为是子序列，所以可以从dp[q[0]]跳转过来，也可以前面的元素都不要\n",
    "                dp[i] += dp[q[0]] if dp[q[0]] > 0 else 0\n",
    "            if q and i - q[0] >= k:\n",
    "                q.popleft()\n",
    "            while q and dp[q[-1]] <= dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        max_=max(nums)\n",
    "\n",
    "        dq=deque(maxlen=k)\n",
    "\n",
    "\n",
    "        f=[]\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            cur=nums[i]\n",
    "            \n",
    "\n",
    "            if(len(dq)!=0 and i-dq[0]>k):\n",
    "                dq.popleft()\n",
    "\n",
    "            max_before=0 if len(dq)==0 else f[dq[0]]\n",
    "\n",
    "            if(max_before>0):\n",
    "                local_=max_before+cur\n",
    "            else:\n",
    "                local_=cur\n",
    "\n",
    "            \n",
    "           \n",
    "\n",
    "            while(len(dq)!=0 and local_>f[dq[-1]]):\n",
    "                dq.pop()\n",
    "\n",
    "            \n",
    "            #if(len(dq)==0 or local_<=f[dq[-1]]):\n",
    "\n",
    "            dq.append(i)\n",
    "            \n",
    "            #print(dq)\n",
    "            max_=max(max_,local_)\n",
    "\n",
    "            f.append(local_)\n",
    "\n",
    "            #print(f)\n",
    "          \n",
    "        return max_\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [nums[i] for i in range(n)] \n",
    "        dq = collections.deque()\n",
    "        for i in range(n):\n",
    "            while dq and i - dq[0] > k:\n",
    "                dq.popleft()\n",
    "            if dq:\n",
    "                dp[i] = max(dp[i], dp[dq[0]] + nums[i])\n",
    "            while dq and dp[i] >= dp[dq[-1]]:\n",
    "                dq.pop()\n",
    "            dq.append(i)\n",
    "        return max(dp)\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = deque()\n",
    "        dp = [num for num in nums]\n",
    "        for i in range(n):\n",
    "            if q:\n",
    "                dp[i] += dp[q[0]] if dp[q[0]] > 0 else 0\n",
    "            if q and i - q[0] >= k:\n",
    "                q.popleft()\n",
    "            while q and dp[q[-1]] <= dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        q = deque()\n",
    "        dp = [num for num in nums]\n",
    "        res = nums[0]\n",
    "        for i in range(n):\n",
    "            if q:\n",
    "                dp[i] += dp[q[0]] if dp[q[0]] > 0 else 0\n",
    "            if q and i - q[0] >= k:\n",
    "                q.popleft()\n",
    "            while q and dp[q[-1]] <= dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=nums[0]\n",
    "        res=nums[0]\n",
    "        q=deque([nums[0]])\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dp[i]=max(nums[i],q[0]+nums[i])\n",
    "            res=max(res,dp[i])\n",
    "            if i>=k:\n",
    "                if q[0]==dp[i-k]:\n",
    "                    q.popleft()\n",
    "            while q and q[-1]<dp[i]:\n",
    "                q.pop()\n",
    "            q.append(dp[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        dp = [0] * (len(nums) + 1)\n",
    "        ans = nums[0]\n",
    "        queue = deque([0])\n",
    "        for i in range(1, len(nums) + 1):\n",
    "            dp[i] = max(dp[queue[0]], 0) + nums[i - 1]\n",
    "            while len(queue) > 0 and dp[queue[-1]] <= dp[i]:\n",
    "                queue.pop()\n",
    "            queue.append(i)\n",
    "            if queue[0] <= i - k:\n",
    "                queue.popleft()\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        numsSize = len(nums)\n",
    "\n",
    "        monotonicDeque = deque()\n",
    "        dp = [0] * numsSize\n",
    "\n",
    "        for i in range(numsSize):\n",
    "            if monotonicDeque and i - monotonicDeque[0] > k:\n",
    "                monotonicDeque.popleft()\n",
    "\n",
    "            dp[i] = (dp[monotonicDeque[0]] if monotonicDeque else 0) + nums[i]\n",
    "            while monotonicDeque and dp[monotonicDeque[-1]] < dp[i]:\n",
    "                monotonicDeque.pop()\n",
    "\n",
    "            if dp[i] > 0:\n",
    "                monotonicDeque.append(i)\n",
    "\n",
    "        retVal = max(dp)\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 存储动态规划结果的数组\n",
    "        # 我们直接放入 f[0] 的值，防止处理边界情况\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "        # 单调队列\n",
    "        # 一开始唯一的 j 为 0\n",
    "        q = collections.deque([0])\n",
    "        \n",
    "        ans = nums[0]\n",
    "        for i in range(1, n):\n",
    "            # 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            # 此时队首的 j 即为最优的 j 值\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            ans = max(ans, f[i])\n",
    "            # 维护队列的单调性，不断从队尾弹出元素\n",
    "            while q and f[i] >= f[q[-1]]:\n",
    "                q.pop()\n",
    "            # 将 i 作为之后的新 j 值放入队尾\n",
    "            q.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [nums[0]] + [0] * (n-1)\n",
    "        q = collections.deque([0])\n",
    "\n",
    "        ans =nums[0]\n",
    "        for i  in range(1,n):\n",
    "            while q and i-q[0] > k:\n",
    "                q.popleft()\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            ans = max(ans, f[i])\n",
    "            while q and f[i] >= f[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        deque = collections.deque(maxlen=k)   \n",
    "        dp[0] = nums[0]\n",
    "        deque.append(0)\n",
    "        for i in range(1, n):\n",
    "            dp[i] = nums[i] + max(0, dp[deque[0]])\n",
    "            if i >= k:\n",
    "                while deque and i - deque[0] >= k:\n",
    "                    deque.popleft()\n",
    "            while deque and dp[i] >= dp[deque[-1]]:\n",
    "                deque.pop()\n",
    "            deque.append(i) \n",
    "        #print(dp)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        dp,q=[nums[0]]+[0]*(len(nums)-1),collections.deque([0])\n",
    "        for i in range(1,len(nums)):\n",
    "            while q and q[0]<i-k:q.popleft()\n",
    "            dp[i]=nums[i]+max(dp[q[0]],0)\n",
    "            while q and dp[i]>=dp[q[-1]]:q.pop()\n",
    "            q.append(i)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "单调栈\n",
    "'''\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        st = collections.deque()\n",
    "        dp = [0] * n\n",
    "        for i in range(n):\n",
    "            while st and st[0] < i - k:\n",
    "                st.popleft()\n",
    "\n",
    "            dp[i] = nums[i]    \n",
    "            if st and dp[st[0]] > 0:\n",
    "                dp[i] += dp[st[0]]\n",
    "            \n",
    "            while st and dp[i] >= dp[st[-1]]:\n",
    "                st.pop()\n",
    "\n",
    "            st.append(i)\n",
    "        return max(dp)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 需要一个单调递减的队列\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        mx = max(nums)\n",
    "        if mx <= 0:\n",
    "            return mx\n",
    "        n = len(nums)\n",
    "        ans = nums[0]\n",
    "        f = [0] * n\n",
    "        f[0] = nums[0]\n",
    "        q = deque()\n",
    "        q.append(0)\n",
    "        for i in range(1, n):\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            f[i] = max(f[q[0]] + nums[i], nums[i])\n",
    "            ans = max(ans, f[i])\n",
    "            while q and f[q[-1]] <= f[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 存储动态规划结果的数组\n",
    "        # 我们直接放入 f[0] 的值，防止处理边界情况\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "        # 单调队列\n",
    "        # 一开始唯一的 j 为 0\n",
    "        q = collections.deque([0])\n",
    "        \n",
    "        ans = nums[0]\n",
    "        for i in range(1, n):\n",
    "            # 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            # 此时队首的 j 即为最优的 j 值\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            ans = max(ans, f[i])\n",
    "            # 维护队列的单调性，不断从队尾弹出元素\n",
    "            while q and f[i] >= f[q[-1]]:\n",
    "                q.pop()\n",
    "            # 将 i 作为之后的新 j 值放入队尾\n",
    "            q.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        dp = [0]*len(nums)\n",
    "        q = deque()\n",
    "        dp[0] = nums[0]\n",
    "        q.append(0)\n",
    "        res = dp[0]\n",
    "        for i in range(1,len(nums)):\n",
    "            dp[i] = max(dp[q[0]] + nums[i],nums[i])\n",
    "            res = max(res,dp[i])\n",
    "            while q and i - q[0] >= k:\n",
    "                q.popleft()\n",
    "            while q and dp[q[-1]] <= dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 存储动态规划结果的数组\n",
    "        # 我们直接放入 f[0] 的值，防止处理边界情况\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "        # 单调队列\n",
    "        # 一开始唯一的 j 为 0\n",
    "        q = collections.deque([0])\n",
    "        \n",
    "        ans = nums[0]\n",
    "        for i in range(1, n):\n",
    "            # 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            # 此时队首的 j 即为最优的 j 值\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            ans = max(ans, f[i])\n",
    "            # 维护队列的单调性，不断从队尾弹出元素\n",
    "            while q and f[i] >= f[q[-1]]:\n",
    "                q.pop()\n",
    "            # 将 i 作为之后的新 j 值放入队尾\n",
    "            q.append(i)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        q = deque([0])\n",
    "        n = len(nums)\n",
    "        f = [0] * (n + 1)\n",
    "        nums = nums\n",
    "        for i in range(n):\n",
    "            f[i] = nums[i]\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            f[i] = max(f[i], f[q[0]] + nums[i])\n",
    "            while q and f[q[-1]] <= f[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "            if q[0] <= i - k:\n",
    "                q.popleft()\n",
    "            res = max(res, f[i])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [nums[0]] + [0] * (n - 1)\n",
    "        q = deque([0])\n",
    "        ans = dp[0]\n",
    "\n",
    "        for i in range(1, n) :\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            dp[i] = max(dp[q[0]], 0) + nums[i]\n",
    "\n",
    "            ans = max(ans, dp[i])\n",
    "\n",
    "            while q and dp[i] >= dp[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        q = deque()\n",
    "        ans = nums[0]\n",
    "        for idx, num in enumerate(nums):\n",
    "            while len(q) and (idx - q[0]) > k:\n",
    "                q.popleft()\n",
    "            if len(q):\n",
    "                dp[idx] = num + max(dp[q[0]], 0)\n",
    "            else:\n",
    "                dp[idx] = num\n",
    "            ans = max(dp[idx], ans)\n",
    "            while len(q) and dp[idx] > dp[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(idx)\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        q = collections.deque()\n",
    "        dp[0] = nums[0]\n",
    "        q.append(0)\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = max(dp[q[0]], 0) + nums[i]\n",
    "            if q[0] == i-k: \n",
    "                q.popleft()\n",
    "            while q and dp[q[-1]] < dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        stack = collections.deque(maxlen=k)\n",
    "        stack.append(0)\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = max(0, dp[stack[0]]) + nums[i]\n",
    "            if i >= k:\n",
    "                while stack and i - stack[0] >= k:\n",
    "                    stack.popleft()\n",
    "            while stack and dp[i] >= dp[stack[-1]]:\n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 存储动态规划结果的数组\n",
    "        # 我们直接放入 f[0] 的值，防止处理边界情况\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "        # 单调队列\n",
    "        # 一开始唯一的 j 为 0\n",
    "        q = collections.deque([0])\n",
    "        \n",
    "        ans = nums[0]\n",
    "        for i in range(1, n):\n",
    "            # 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            # 此时队首的 j 即为最优的 j 值\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            ans = max(ans, f[i])\n",
    "            # 维护队列的单调性，不断从队尾弹出元素\n",
    "            while q and f[i] >= f[q[-1]]:\n",
    "                q.pop()\n",
    "            # 将 i 作为之后的新 j 值放入队尾\n",
    "            q.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        # dp = [0] * len(nums)\n",
    "        # dp[0] = nums[0]\n",
    "        # for i in range(1, len(nums)):\n",
    "        #     max_value = 0\n",
    "        #     for j in range(1,k+1):\n",
    "        #         if (i-j >= 0):\n",
    "        #             max_value = max(max_value, dp[i-j])\n",
    "        #     dp[i] = nums[i] + max_value\n",
    "        # return max(dp)\n",
    "        queue = deque()\n",
    "        dp = [0] * len(nums)\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if queue and i - queue[0] > k:\n",
    "                queue.popleft()\n",
    "            \n",
    "            dp[i] = (dp[queue[0]] if queue else 0) + nums[i]\n",
    "            while queue and dp[queue[-1]] < dp[i]:\n",
    "                queue.pop()\n",
    "            \n",
    "            if dp[i] > 0:\n",
    "                queue.append(i)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "        q = deque([0])\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            res = max(res, f[i])\n",
    "            while q and f[q[-1]] <= f[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-1]*n\n",
    "        # 以 i 结尾的子序列最大值\n",
    "        # 利用单调队列维护区间[i-k,i-1]的最大值，加速DP\n",
    "        max_res = nums[0]\n",
    "        dp[0] = nums[0]\n",
    "        window = [0]\n",
    "        for i in range(1,n):\n",
    "            dp[i] = nums[i] + max(0, dp[window[0]])\n",
    "            max_res = max(max_res, dp[i])\n",
    "            if window[0]<i-k+1:\n",
    "                window.pop(0)\n",
    "            cur = dp[i]\n",
    "            while window and cur>=dp[window[-1]]:\n",
    "                window.pop(-1)\n",
    "            window.append(i)\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        # - dp[i] is max sum of subset and must include nums[i]\n",
    "        # - formula is: dp[i] = max(dp[i-1], dp[i-2], ..., dp[i-k], 0) + nums[i]\n",
    "        dp = [0] * len(nums)\n",
    "        \n",
    "        # - monotonic queue and keep index of dp[]\n",
    "        # - q[0] is the index of max dp[]\n",
    "        q = collections.deque()\n",
    "        \n",
    "        # - init dp and q\n",
    "        dp[0] = nums[0]\n",
    "        q.append(0)\n",
    "        \n",
    "        # - from 1 to n-1\n",
    "        for i in range(1, len(nums)):\n",
    "            # - update dp[i]\n",
    "            dp[i] = max(dp[q[0]], 0) + nums[i]\n",
    "\n",
    "            # - if window slide, pop the left most index\n",
    "            if q[0] == i-k: \n",
    "                q.popleft()\n",
    "\n",
    "            # - update q, pop all elements which less than current one\n",
    "            while q and dp[q[-1]] < dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "        return max(dp)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "f[i] 表示在数组的前 i 个数中进行选择，并且恰好选择了第 i 个数，可以得到的最大和。\n",
    "'''\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 存储动态规划结果的数组\n",
    "        # 我们直接放入 f[0] 的值，防止处理边界情况\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "        # 单调队列\n",
    "        # 一开始唯一的 j 为 0\n",
    "        q = collections.deque([0])\n",
    "        \n",
    "        ans = nums[0]\n",
    "        for i in range(1, n):\n",
    "            # 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            # 此时队首的 j 即为最优的 j 值\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            ans = max(ans, f[i])\n",
    "            # 维护队列的单调性，不断从队尾弹出元素\n",
    "            while q and f[i] >= f[q[-1]]:\n",
    "                q.pop()\n",
    "            # 将 i 作为之后的新 j 值放入队尾\n",
    "            q.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * (n)\n",
    "        q = deque()\n",
    "        for i, val in enumerate(nums):\n",
    "            f[i] = nums[i]\n",
    "            while q and i - q[0][0] > k:\n",
    "                q.popleft()\n",
    "\n",
    "            res = -inf\n",
    "            if q: res = q[0][1]\n",
    "            f[i] = max(f[i], res + nums[i])\n",
    "\n",
    "            while q and q[-1][1] <= f[i]:\n",
    "                q.pop()\n",
    "            \n",
    "            q.append((i, f[i]))\n",
    "            #print(i, f, q)\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 存储动态规划结果的数组\n",
    "        # 我们直接放入 f[0] 的值，防止处理边界情况\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "        # 单调队列\n",
    "        # 一开始唯一的 j 为 0\n",
    "        q = collections.deque([0])\n",
    "        \n",
    "        ans = nums[0]\n",
    "        for i in range(1, n):\n",
    "            # 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            # 此时队首的 j 即为最优的 j 值\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            ans = max(ans, f[i])\n",
    "            # 维护队列的单调性，不断从队尾弹出元素\n",
    "            while q and f[i] >= f[q[-1]]:\n",
    "                q.pop()\n",
    "            # 将 i 作为之后的新 j 值放入队尾\n",
    "            q.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp, q, res = [nums[0]] * n, deque([0]), nums[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = nums[i] + max(0, dp[q[0]])\n",
    "            while q and dp[i] > dp[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "            if q and i - q[0] + 1 > k:\n",
    "                q.popleft()\n",
    "            res = max(res, dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = nums[0]\n",
    "        maxDeque = deque([0])   # monotonic decreasing dequeue, element: index of number in dp array\n",
    "        dp = [0] * n    # dp[i]: max sum of subsequence ended at nums[i]\n",
    "        dp[0] = nums[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            while maxDeque and i-maxDeque[0] > k:\n",
    "                maxDeque.popleft()\n",
    "            \n",
    "            dp[i] = nums[i] + max(0, dp[maxDeque[0]])\n",
    "\n",
    "            ans = max(ans, dp[i])\n",
    "\n",
    "            while maxDeque and dp[maxDeque[-1]]<= dp[i]:\n",
    "                maxDeque.pop()\n",
    "            \n",
    "            maxDeque.append(i)\n",
    "        \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 存储动态规划结果的数组\n",
    "        # 我们直接放入 f[0] 的值，防止处理边界情况\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "        # 单调队列\n",
    "        # 一开始唯一的 j 为 0\n",
    "        q = collections.deque([0])\n",
    "        \n",
    "        ans = nums[0]\n",
    "        for i in range(1, n):\n",
    "            # 如果队首的 j 与 i 的差值大于 k，则不满足要求，弹出\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            # 此时队首的 j 即为最优的 j 值\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            ans = max(ans, f[i])\n",
    "            # 维护队列的单调性，不断从队尾弹出元素\n",
    "            while q and f[i] >= f[q[-1]]:\n",
    "                q.pop()\n",
    "            # 将 i 作为之后的新 j 值放入队尾\n",
    "            q.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        dp = [0] * n\n",
    "\n",
    "        q = deque()\n",
    "        dp[0] = nums[0]\n",
    "        q.append(0)\n",
    "\n",
    "        for i in range(1, n):\n",
    "            if q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "\n",
    "            dp[i] = nums[i] + max(0, dp[q[0]])\n",
    "            while q and dp[q[-1]] < dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = nums.copy()\n",
    "        ans = -inf\n",
    "        stack = deque()\n",
    "        for i in range(len(nums)):\n",
    "            if stack:\n",
    "                dp[i] = max(dp[i], dp[i] + dp[stack[0]])\n",
    "            while stack and (dp[i] > dp[stack[-1]]):\n",
    "                stack.pop()\n",
    "            if stack and i - stack[0] >= k:\n",
    "                stack.popleft()\n",
    "            stack.append(i)\n",
    "            ans = max(ans, dp[i])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        dp[0]=nums[0]\n",
    "        res=nums[0]\n",
    "        q=deque([nums[0]])\n",
    "\n",
    "        for i in range(1,n):\n",
    "            dp[i]=max(nums[i],q[0]+nums[i])\n",
    "            res=max(res,dp[i])\n",
    "            if i>=k:\n",
    "                if q[0]==dp[i-k]:\n",
    "                    q.popleft()\n",
    "            while q and q[-1]<dp[i]:\n",
    "                q.pop()\n",
    "            q.append(dp[i])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [nums[0]] + [0] * (n - 1)\n",
    "        q = collections.deque([0])\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            dp[i] = max(dp[q[0]], 0) + nums[i]\n",
    "            res = max(res, dp[i])\n",
    "            while q and dp[i] >= dp[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp, q, res = [nums[0]] * n, deque([0]), nums[0]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = nums[i] + max(0, dp[q[0]])\n",
    "            while q and dp[i] > dp[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "            if q and i - q[0] + 1 > k:\n",
    "                q.popleft()\n",
    "            res = max(res, dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        # dp[i] 存储的是以 nums[i] 结尾的满足条件的子序列的最大和\n",
    "        dp = [0] * len(nums)\n",
    "        dp[0] = nums[0]\n",
    "        max_sum = dp[0]\n",
    "\n",
    "        # 使用双端队列来存储滑动窗口内的元素的下标\n",
    "        dq = collections.deque()\n",
    "        dq.append(0)\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = nums[i]\n",
    "\n",
    "            # 如果窗口的最左边的元素还是有效的，那么更新 dp[i]\n",
    "            if dq and dq[0] == i - k - 1:\n",
    "                dq.popleft()\n",
    "\n",
    "            # 只有当双端队列不为空时，我们才更新 dp[i]\n",
    "            if dq:\n",
    "                dp[i] = max(dp[i], dp[dq[0]] + nums[i])\n",
    "\n",
    "            # 更新最大值\n",
    "            max_sum = max(max_sum, dp[i])\n",
    "\n",
    "            # 更新双端队列，确保其内的元素是非递减的\n",
    "            while dq and dp[i] >= dp[dq[-1]]:\n",
    "                dq.pop()\n",
    "            dq.append(i)\n",
    "\n",
    "        return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "        q = deque([0])\n",
    "        res = nums[0]\n",
    "        for i in range(1, n):\n",
    "            while q and i - q[0] > k:\n",
    "                q.popleft()\n",
    "            f[i] = max(f[q[0]], 0) + nums[i]\n",
    "            res = max(res, f[i])\n",
    "            while q and f[q[-1]] <= f[i]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [-1]*n\n",
    "        # 以 i 结尾的子序列最大值\n",
    "        # 利用单调队列维护区间[i-k,i-1]的dp最大值，加速DP\n",
    "        max_res = nums[0]\n",
    "        dp[0] = nums[0]\n",
    "        window = [0]\n",
    "        for i in range(1,n):\n",
    "            dp[i] = nums[i] + max(0, dp[window[0]])\n",
    "            max_res = max(max_res, dp[i])\n",
    "            if window[0]<i-k+1:\n",
    "                window.pop(0)\n",
    "            cur = dp[i]\n",
    "            while window and cur>=dp[window[-1]]:\n",
    "                window.pop(-1)\n",
    "            window.append(i)\n",
    "        return max_res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        dp = [0] * len(nums)#动态规划，dp[i]存放以nums[i]结尾的子序列最大和\n",
    "        q = collections.deque()#双向链表，q[0]表示dp[i-k,i-1]中最大值的索引\n",
    "        dp[0] = nums[0]#初始化\n",
    "        q.append(0)#初始化\n",
    "        for i in range(1, len(nums)):\n",
    "            dp[i] = max(dp[q[0]], 0) + nums[i]\n",
    "            if q[0] == i-k: \n",
    "                q.popleft()\n",
    "            while q and dp[q[-1]] < dp[i]:\n",
    "                q.pop()#小于滑窗下一步将要加入的dp[i]的子序列和均删掉\n",
    "            #q的取法导致dp[q[]]是一个单调递减的序列,dp[q[0]]永远是dp[i-k,i-1]中的最大值\n",
    "            q.append(i)#若都小于，则当前dp[i]就是第i+1步滑窗以nums[i]结尾子序列的最大和，对应q[0]=i\n",
    "        return max(dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=nums[0]\n",
    "        dp=[0]*n\n",
    "        q=deque()##单调队列\n",
    "        for i in range(n):\n",
    "            if i>k and q[0]<i-k:\n",
    "                ans=max(ans,dp[q.popleft()])\n",
    "            dp[i] = nums[i] + max(0, dp[q[0]]) if q else nums[i]\n",
    "            # ans=max(ans,dp[i])\n",
    "            while q and dp[q[-1]]<dp[i]:\n",
    "                q.pop()\n",
    "            q.append(i)      \n",
    "        return max(ans,max(dp[i] for i in q))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    \"\"\"\r\n",
    "        Dynamic Programming\r\n",
    "    \"\"\"\r\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        dp = [0] * n\r\n",
    "        dp[0] = nums[0]\r\n",
    "        q = deque()\r\n",
    "        q.append(0)\r\n",
    "        ans = nums[0]\r\n",
    "        for i in range(1, n):\r\n",
    "            while q and i - q[0] > k: # pop the out-of-range index\r\n",
    "                q.popleft()\r\n",
    "            dp[i] = max(nums[i], nums[i] + dp[q[0]])\r\n",
    "            ans = max(ans, dp[i])\r\n",
    "            while q and dp[i] >= dp[q[-1]]:\r\n",
    "                q.pop()\r\n",
    "            q.append(i)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n  = len(nums)\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "\n",
    "        ans = nums[0]\n",
    "        # 单调队列主要存储的是索引信息\n",
    "        q = collections.deque([0])\n",
    "\n",
    "        for i in range(1,n):\n",
    "            while q and i-q[0]>k:\n",
    "                q.popleft()\n",
    "            \n",
    "            f[i] = max(f[q[0]],0)+nums[i]\n",
    "            #ans = max(ans, f[i])\n",
    "\n",
    "            while q and f[i]>=f[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n  = len(nums)\n",
    "        f = [nums[0]] + [0] * (n - 1)\n",
    "\n",
    "        ans = nums[0]\n",
    "        # 单调队列主要存储的是索引信息\n",
    "        q = collections.deque([0])\n",
    "\n",
    "        for i in range(1,n):\n",
    "            while q and i-q[0]>k:\n",
    "                q.popleft()\n",
    "            \n",
    "            f[i] = max(f[q[0]],0)+nums[i]\n",
    "            ans = max(ans, f[i])\n",
    "\n",
    "            while q and f[i]>=f[q[-1]]:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = nums[0]\n",
    "        queue = collections.deque([(nums[0], 0)])\n",
    "        dp = None\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            while queue and i - queue[0][1] > k:\n",
    "                queue.popleft()\n",
    "\n",
    "            # if pq and i - pq[0][1] <= k:\n",
    "            val, idx = queue[0]\n",
    "\n",
    "            if val < 0:\n",
    "                dp = nums[i]\n",
    "            else:\n",
    "                dp = val + nums[i]\n",
    "\n",
    "            while queue and queue[-1][0] < dp:\n",
    "                queue.pop()\n",
    "\n",
    "            queue.append((dp, i))\n",
    "\n",
    "            ans = max(ans, dp)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        ans=nums[0]\n",
    "        q=deque()##单调队列\n",
    "        for i in range(n):\n",
    "            if i>k and q[0][0]<i-k:\n",
    "                ans=max(ans,q.popleft()[1])\n",
    "            t=nums[i] + max(0, q[0][1]) if q else nums[i]\n",
    "            while q and q[-1][1]<t:\n",
    "                q.pop()\n",
    "            q.append((i,t))      \n",
    "        return max(ans,max(dp for j,dp in q))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 定义：dp[i] 表示以 nums[i] 结尾的子序列的最大和\n",
    "        dp = [0] * n\n",
    "        dp[0] = nums[0]\n",
    "        # 单调队列辅助计算 dp[i-k..i-1] 的最大值\n",
    "        window = [(nums[0], 0)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            # 状态转移方程\n",
    "            if window and i - k > window[0][1]:\n",
    "                window.pop(0)\n",
    "\n",
    "            if window:\n",
    "                dp[i] = max(nums[i], window[0][0] + nums[i])\n",
    "            else:\n",
    "                dp[i] = nums[i]\n",
    "\n",
    "            while window and window[-1][0] < dp[i]:\n",
    "                window.pop()\n",
    "\n",
    "            window.append((dp[i], i))\n",
    "\n",
    "        # dp 数组中的最大值就是结果\n",
    "        res = max(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        dp = [0]*n\n",
    "        dp[0] = nums[0]\n",
    "        \n",
    "        queue = collections.deque()\n",
    "        queue.append(0)\n",
    "        \n",
    "        '''\n",
    "        第一部分\n",
    "            在实现技巧上，要先遍历前k个数。\n",
    "            在这里就要 对 前k个dp 先算出来。\n",
    "        第二部分\n",
    "            一边更新dp，一边更新queue（把dp放进去）\n",
    "            dp[queue[0]] 取代的就是 dp[i-j] for j in range(1,k+1)\n",
    "        现在合并\n",
    "        '''\n",
    "        for i in range(1,n): # 想看正确但是会超时的答案的话，把k改成n\n",
    "            while queue and i-queue[0]>k:\n",
    "                queue.popleft()\n",
    "                \n",
    "            dp[i] = max(nums[i],dp[queue[0]]+nums[i])\n",
    "            \n",
    "            while queue and dp[i]>dp[queue[-1]]:\n",
    "                queue.pop()\n",
    "                \n",
    "            queue.append(i)\n",
    "            \n",
    "        print(dp)\n",
    "        return(max(dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * n\n",
    "        q = deque()\n",
    "        for i in range(n):\n",
    "            while q and i - q[0][0] > k:\n",
    "                q.popleft()\n",
    "            if not q:\n",
    "                f[i] = nums[i]\n",
    "            else:\n",
    "                # 求 子序列和\n",
    "                f[i] = max(q[0][1], 0) + nums[i]\n",
    "            while q and f[i] >= q[-1][1]:\n",
    "                q.pop()\n",
    "            q.append([i, f[i]])\n",
    "        print(f)\n",
    "        return max(f)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        dq = deque()\n",
    "        ans = -inf\n",
    "        for i, n in enumerate(nums):\n",
    "            if len(dq) and i - dq[0][0] > k:\n",
    "                dq.popleft()\n",
    "            if len(dq) and dq[0][1] > 0:\n",
    "                n += dq[0][1]\n",
    "            if n > ans:\n",
    "                ans = n\n",
    "            while len(dq) and n > dq[-1][1]:\n",
    "                dq.pop()\n",
    "            dq.append([i, n])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        que=deque()\n",
    "        que.append([0,nums[0]])\n",
    "        n=len(nums)\n",
    "        res=nums[0]\n",
    "        for i in range(1,n):\n",
    "            while que and i-que[0][0]>k:\n",
    "                que.popleft()\n",
    "            if que:\n",
    "                ans=max(0,que[0][1])+nums[i]\n",
    "            else:\n",
    "                ans=nums[i]\n",
    "            res=max(res,ans)\n",
    "            while que and ans>que[-1][1]:\n",
    "                que.pop()\n",
    "            que.append([i,ans])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [0] * n\n",
    "        q = deque()\n",
    "        for idx, num in enumerate(nums):\n",
    "            while len(q) and (idx - q[0][0]) > k:\n",
    "                q.popleft()\n",
    "            if len(q):\n",
    "                dp[idx] = num + max(q[0][1], 0)\n",
    "            else:\n",
    "                dp[idx] = num\n",
    "            while len(q) and dp[idx] > q[-1][1]:\n",
    "                q.pop()\n",
    "            q.append([idx, dp[idx]])\n",
    "        \n",
    "        return max(dp)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = nums[0]\n",
    "        pq = []\n",
    "        heapq.heappush(pq, (-nums[0], 0))\n",
    "        dp = None\n",
    "\n",
    "        for i in range(1, len(nums)):\n",
    "            while pq and i - pq[0][1] > k:\n",
    "                heapq.heappop(pq)\n",
    "\n",
    "            # if pq and i - pq[0][1] <= k:\n",
    "            val, idx = pq[0]\n",
    "            val *= -1\n",
    "            if val < 0:\n",
    "                dp = nums[i]\n",
    "            else:\n",
    "                dp = val + nums[i]\n",
    "\n",
    "            heapq.heappush(pq, (-dp, i))\n",
    "            ans = max(ans, dp)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        ans=99999999;pq=[]\n",
    "        for i,j in enumerate(nums):\n",
    "            while(len(pq) and pq[0][1]<i-k):heapq.heappop(pq)\n",
    "            if(len(pq) and pq[0][0]<0):ans=min(ans,pq[0][0]-j);heapq.heappush(pq,(pq[0][0]-j,i))\n",
    "            else:ans=min(ans,-j);heapq.heappush(pq,(-j,i))\n",
    "        return -ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        n=len(nums)\n",
    "        pq=[]\n",
    "        res=inf\n",
    "        for i in range(n):\n",
    "            while pq and pq[0][1]<i-k: heappop(pq)\n",
    "            cs=(min(0,pq[0][0]) if pq else 0)-nums[i]\n",
    "            res=min(res,cs)\n",
    "            heappush(pq,(cs,i))\n",
    "        return -res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        heap = [(-nums[0], 0)]\n",
    "        ans = nums[0]\n",
    "        \n",
    "        for i in range(1, len(nums)):\n",
    "            while i - heap[0][1] > k:\n",
    "                heapq.heappop(heap)\n",
    "\n",
    "            curr = max(0, -heap[0][0]) + nums[i]\n",
    "            ans = max(ans, curr)\n",
    "            heapq.heappush(heap, (-curr, i))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:\n",
    "        ans = -inf\n",
    "        q = []\n",
    "        for j, v in enumerate(nums):\n",
    "            t = -inf\n",
    "            while q and j - q[0][1] > k:\n",
    "                heappop(q)\n",
    "            if q:\n",
    "                t = -q[0][0]\n",
    "            t = max(t + v, v)\n",
    "            ans = max(ans, t)\n",
    "            heappush(q, (-t, j))\n",
    "            # print(j, v, t)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
